HW#3 --- last modified January 28 2019 19:01:03..

Solution set.

Due date: Oct 19

Files to be submitted:
  Hw3.zip

Purpose: To get familiar with our BCNF and 3NF decomposition algorithms, to practice modeling using ER diagrams.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

Know the algorithms for testing if a decomposition is in a given normal form and the algorithms which given a set of functional dependencies can do table decomposition into 3NF or BCNF

Specification:

This homework will consists of two parts a written part which you submit in a file Hw3.pdf and a coding part ThirdNormalForm.java. These files should be submitted together with a readme.txt containing your group members in the file Hw3.zip that you will submit.

For the written exercises do the following problems:

1. For each of Exercise 3.3.1 (a) and (b) add one nontrivial FD to those listed, then do the problem.
2. Exercise 3.4.1 (a) and (b).
3. Exercise 3.6.1. Make sure to explain why we know the tuples are in `R` to receive credit.
4. Imagine you are tasked with coming up with a new Virtual Reality Movie Website. VR movies can be 180, 360 with or without 3D. People might want to have accounts to comment on Movies. Make an E/R diagram that might be suitable for the database of such a site and include it in your Hw3.pdf.

For the coding part of your homework, you will write a program to decompose a table into 3NF relations with the lossless join and dependency preservation properties. Your code should be based off the algorithm from class (Algorithm 3.26 in the book). The grader will compile your program from the command line with a line like:

javac ThirdNormalForm.java

The grader will then run your program with a line like:

java ThirdNormalForm some_file

Here some_file is the name of a text file containing a list of functional dependencies. To be more specific the test files will consist of sequences of lines delimited by a single newline character (\n). Each line will contain a sequence of comma separated integers followed by a semicolon followed by another comma separated list of integers. As an example, the grader might type:

java ThirdNormalForm test1.txt

1,2;3
3;2
1;4
5;5

In the above, each integer `i` corresponds to an attribute `A_i`. The line `1,2;3` should be interpreted as the functional dependency: `A_1A_2 ->A_3`. If the largest integer in the file is `n`, then the relation to be split into 3NF is assumed to be `R(A_1,A_2, ..., A_n)`. For the example above, the relation to decompose would be `R(A_1,A_2,A_3,A_4,A_5)`. On such an input your program should output a sequence of lines delimited by newline characters. These lines should contain a comma separted list of integers corresponding to one relation in the 3NF decomposition. For the example above, your program should output:

1,2,3
1,4
1,2,5

This corresponds to the relations `S(A_1, A_2, A_3)`, `T(A_1, A_4)`, `U(A_1, A_2, A_5)`, which is a 3NF lossless join and dependency preserving decomposition.

Point Breakdown